package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Unknown;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Map;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * https://leetcode.com/problems/validate-stack-sequences/
 * Given two sequences pushed and popped with distinct values, return true if and only if
 * this could have been the result of a sequence of push and pop operations on an initially empty stack.
 * <p>
 * 0 <= pushed.length == popped.length <= 1000
 * 0 <= pushed[i], popped[i] < 1000
 * pushed is a permutation of popped.
 * pushed and popped have distinct values.
 */
public class LC946 implements Unknown {

    //Input: pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
    //Output: true
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        LinkedList<Integer> stack = new LinkedList<>();
        Map<Integer, Integer> index = IntStream.range(0, pushed.length).boxed()
                .collect(Collectors.toMap(i -> pushed[i], i -> i));
        int inStack = -1;//pushed数组中当前已在栈的元素下标
        for (int i = 0; i < popped.length; i++) {
            int ele = popped[i];
            int eleIndex = index.get(ele);
            if (eleIndex > inStack) {//当前要判断的元素 在还没入栈的范围
                for (int j = inStack + 1; j < eleIndex; j++) {//之前的全入栈, 当前元素不用了
                    stack.addLast(pushed[j]);
                }
                inStack = eleIndex;
            } else {//当前要判断的元素已经在入栈的范围, 只有一个原因, 比他往后的人要入栈导致他提前入栈了
                int pop = stack.removeLast();
                if (pop != ele) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(new LC946().validateStackSequences(new int[]{1, 2, 3, 4, 5}, new int[]{4, 5, 3, 2, 1}));
        System.out.println(new LC946().validateStackSequences(new int[]{1, 2, 3, 4, 5}, new int[]{4, 5, 1, 2, 3}));
        System.out.println(new LC946().validateStackSequences(new int[]{1, 2, 3, 4, 5}, new int[]{3, 4, 5, 2, 1}));
    }
}
